#include "../tools.h"



class Solution {
public:
    int helper(vector<int>& nums, int sid, int eid){
        int size = nums.size();
        int dp[size];
        dp[sid] = nums[sid];
        dp[sid + 1] = max(nums[sid], nums[sid + 1]);

        for(int i = sid + 2; i <= eid; ++i){
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[eid];
    }

    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size == 0) return 0;
        if(size == 1) return nums[0];
        if(size == 2) return max(nums[0], nums[1]);

        int res1 = helper(nums, 0, size - 2);
        int res2 = helper(nums, 1, size - 1);
        return max(res1, res2);
    }
};


int main(int argc, char const *argv[])
{
    Solution sol;

    vector<int> nums = {1,2,3,1};

    cout << sol.rob(nums);

    return 0;
}
